#include <iostream>
#include "Charnode.h"
#include "globals.h"
#include "bitops.h"
#include <vector>
#include <map>
#include <fstream>

#ifndef _HuffmanCode_h
#define _HuffmanCode_h

using namespace std;


template <class TYPE>
class Huffman
{
private:
	vector<Charnode<TYPE> *> charactermap;
	Charnode<TYPE> *huffmanTreeRoot;
	map<TYPE, string> table;

	map<TYPE, int> freqtab;

private:
	void process_file(const char *filename , map<TYPE,int> & charmap);

	vector<Charnode<TYPE> *> convertToVector(map<TYPE,int> &chamap);


	bool compare(Charnode<TYPE> *i, Charnode<TYPE> *j);

	void MinHeapify(vector<Charnode<TYPE> *> & charactermap, int i,const int n);

	void BuildMinHeap(vector<Charnode<TYPE> *> &charactermap);

	void buildHuffmanTree();

	void delNode(Charnode<TYPE> *);

public:

	Huffman();

	Huffman(const char *filename);

	~Huffman();

	void createHuffmanTable(Charnode<TYPE> * tree,int code,int height);

	void displayCharactermap();

	void displayHuffmanTable();

	Charnode<TYPE> * getRoot();

	map<TYPE, string> getHuffmanTable();

	map<TYPE, int> getFrequencyMap();

	int getCharVecSize();
};


template<class TYPE>
int Huffman<TYPE>::getCharVecSize()
{
	return charactermap.size();
}


template <class TYPE>
void Huffman<TYPE>::process_file(const char *filename , map<TYPE,int> & charmap)
{
	ibstream infile(filename);

	int inbits;
	while(infile.readbits(BITS_PER_WORD, inbits) != false)
	{
		//cout << (TYPE)inbits;
		charmap[(TYPE)inbits]++;
	}

	LOG("\n\n\nEND\n")
}

template <class TYPE>
vector<Charnode<TYPE> *> Huffman<TYPE>::convertToVector(map<TYPE,int> &chamap)
{
	vector<Charnode<TYPE> *> charactermap;

	for(typename map<TYPE,int>::iterator ii=chamap.begin(); ii!=chamap.end(); ++ii)
	{
		//cout << (*ii).first << ": " << (*ii).second << endl;
		Charnode<TYPE> * ch = new Charnode<TYPE>((*ii).first,(*ii).second);
		charactermap.push_back(ch);
#if DEBUG
		//ch->show();
		if(ch->GetLeft()==NULL && ch->GetRight()==NULL)
			LOG("Leaf Node initialized properly");
#endif
	}

	return charactermap;
}

template <class TYPE>
bool Huffman<TYPE>::compare(Charnode<TYPE> *i, Charnode<TYPE> *j)
{
	return (*i<*j);
}

template <class TYPE>
void Huffman<TYPE>::MinHeapify(vector<Charnode<TYPE> *> & charactermap, int i,const int n)
{
	int left = 2*i + 1;
	int right = left + 1;
	int smallest = -1;

	if( left<n && charactermap[left]->Value()<charactermap[i]->Value())
		smallest = left;
	else
		smallest = i;
	if(right<n && charactermap[right]->Value()<charactermap[smallest]->Value())
			smallest = right;

	if(smallest != i)
	{
		Charnode<TYPE> * temp = charactermap[i];
		charactermap[i] =charactermap[smallest];
		charactermap[smallest] = temp;

		MinHeapify(charactermap,smallest,n);
	}
}

template <class TYPE>
void Huffman<TYPE>::BuildMinHeap(vector<Charnode<TYPE> *> &charactermap)
{
	int n = charactermap.size();
	for(int i = n/2; i>=0 ; i--)
		MinHeapify(charactermap,i,n);
}

template <class TYPE>
void Huffman<TYPE>::buildHuffmanTree()
{
	LOG(__func__);


	vector<Charnode<TYPE> *> charactermap = this->charactermap;			//Duplicate and change

/*	
HUFFMAN (C)
	Refer CLRS (non-unicode characters. )
	*/
	int n = charactermap.size();
	LOG("Size of the char map = "<<n);
	for(int i=1;i<n;i++)
	{
		LOG(i<<"th iteration")
		BuildMinHeap(charactermap);
		Charnode<TYPE> *left = new Charnode<TYPE>(charactermap[0]);
		LOG(left->GetCount());
		charactermap.erase(charactermap.begin()+0);
		BuildMinHeap(charactermap);
		Charnode<TYPE> *right = new Charnode<TYPE>(charactermap[0]);
		charactermap.erase(charactermap.begin()+0);
		LOG(right->GetCount());

		Charnode<TYPE> * z = new Charnode<TYPE>('\0',left->Value()+right->Value());
		z->SetLeft(left);
		z->SetRight(right);

		LOG(z->GetCount())
		LOG(z->GetLeft()->GetCount());
		LOG(z->GetRight()->GetCount());

		charactermap.push_back(z);
	}


	huffmanTreeRoot = charactermap[0];			//Initialize the root;

} 	

template <class TYPE>
Huffman<TYPE>::Huffman()
{}

template <class TYPE>
Huffman<TYPE>::Huffman(const char *filename)
{
	map<TYPE, int> charmap;
	process_file(filename, charmap);
	charactermap = convertToVector(charmap);
	freqtab = charmap;

	buildHuffmanTree();
	createHuffmanTable(huffmanTreeRoot, 0, 0);
}

template <class TYPE>
void Huffman<TYPE>::delNode(Charnode<TYPE> *node)
{
	if(node == NULL)
		return;
	delNode(node->GetLeft());
	delNode(node->GetRight());

	delete node;
}

template <class TYPE>
Huffman<TYPE>::~Huffman()
{
	delNode(huffmanTreeRoot);
	huffmanTreeRoot = NULL;
}

template <class TYPE>
void Huffman<TYPE>::createHuffmanTable(Charnode<TYPE> * tree, int code,int height)
{
	LOG(__func__);
	if(tree==NULL)	//This codition never occurs!
		return;
	if(tree->GetLeft()==NULL && tree->GetRight()==NULL) //Leaf Node: Print the char , count and the code.(code length = height of the node :-))
	{
		//cout<<"Character "<<tree->GetChar()<<'\t'<<"Count = "<<tree->GetCount()<<'\t';
		//cout<<"Code: ";

		string codeString = "";
		for(int j = height-1; j>=0; j--)
		{
			if(code & (1<<j))
			{
				//cout<<'1';
				codeString += "1";
			}
			else
			{
				//cout<<'0';
				codeString += "0";
			}
		}
		//cout<<endl;

		table[tree->GetChar()] = codeString;

		return;

	}
	code = code<<1;
	createHuffmanTable(tree->GetLeft(),code,height+1);
	createHuffmanTable(tree->GetRight(),code|1,height+1);
}

template <class TYPE>
void Huffman<TYPE>::displayCharactermap()
{
	LOG(__func__);
	int n = charactermap.size();
	LOG("Size = "<<n)
	for(int i = 0;i<n;i++)
		charactermap[i]->show();
	cout<<endl;
}	

template <class TYPE>
Charnode<TYPE> * Huffman<TYPE>::getRoot()
{
	return huffmanTreeRoot;
}


template <class TYPE>
void Huffman<TYPE>::displayHuffmanTable()
{
	LOG("HUFFMAN TABLE");
	for(typename map<TYPE, string>::iterator ii=table.begin(); ii!=table.end(); ++ii)
	{
		cout << endl << (*ii).first << "\t" << (*ii).second;
	}
	cout << endl;
}

template <class TYPE>
map<TYPE, string> Huffman<TYPE>::getHuffmanTable()
{
	return table;
}

template <class TYPE>
map<TYPE, int> Huffman<TYPE>::getFrequencyMap()
{
	return freqtab;
}

#endif
